package com.mystudy.leetcode.problem.tree.p_653;

import com.mystudy.leetcode.base.TreeNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @program: infoalgorithm
 * @description: 两数之和IV-输入BST
 * @author: zhouzhilong
 * @create: 2019-07-25 10:25
 **/
public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        //前序遍历,存入hashset，当存在与当前节点的值相加等于k的节点则返回true
        Set<Integer> set = new HashSet();
        return find(root,k,set);

    }

    private boolean find(TreeNode node,int k,Set set){
        if(node == null){
            return false;
        }

        int target = k - node.val;
        if(set.contains(target)){
            return true;
        }
        set.add(node.val);
        boolean leftTarget = find(node.left,k,set);
        if(leftTarget){
            return leftTarget;
        }
        boolean rightTarget = find(node.right,k,set);
        return leftTarget || rightTarget;

    }


}
